% FIXED
\begin{abstract}
Transparency logs allow users to audit a potentially malicious service, paving the way towards a more accountable Internet.
For example, Certificate Transparency (CT) enables domain owners to audit Certificate Authorities (CAs) and detect impersonation attacks.
Yet, to achieve their full potential, transparency logs must be bandwidth-efficient when queried by users.
Specifically, everyone should be able to efficiently \textit{look up} log entries by their key \textit{and} efficiently verify that the log remains \textit{append-only}.
Unfortunately, without additional trust assumptions, current transparency logs cannot provide both small-sized \textit{lookup proofs} and small-sized \textit{append-only proofs}.
In fact, one of the proofs always requires bandwidth linear in the size of the log, making it expensive for everyone to query the log.
In this paper, we address this gap with a new primitive called an \textit{append-only authenticated dictionary} (AAD).
Our construction is the first to achieve (poly)logarithmic size for both proof types and helps reduce bandwidth consumption in transparency logs.
This comes at the cost of increased append times and high memory usage, both of which remain to be improved to make practical deployment possible.
\end{abstract}

% Although it is debatable whether trusting users (e.g., in ~\cite{ect}) qualifies as an "additional trust assumption," since users would be needed for gossip anyway.
% And most users should be honest anyway or have an incentive to be honest, at least in the public-key directory setting.
